package BasicClass.Four;

public class Test_Fourteenth {
    public static void main(String[] args) {

    }

    /**
     * 如何判断两个有环单链表是否相交？相交的话返回第一个相交的节点，不想交的话返回空。如果两个链表长度分别为N和M，请做到时间复杂度O(N+M)，额外空间复杂度O(1)。
     *
     * 给定两个链表的头结点head1和head2(注意，另外两个参数adjust0和adjust1用于调整数据,与本题求解无关)。请返回一个bool值代表它们是否相交。
     *
     * 思路：先获取两个链表的环节点，若环节点相同，那么相交；不同，那就可能不相交或者入环点不同
     * 让其中一个入环点绕环循环一周，若没遇到另一个环点，则不想交
     * @param head1
     * @param head2
     * @param adjust0
     * @param adjust1
     * @return
     */
    public boolean chkInter(ListNode head1, ListNode head2, int adjust0, int adjust1) {
        // write code here
        ListNode loop1 = getLoop(head1);
        ListNode loop2 = getLoop(head2);
        if (loop1 == loop2){
            return true;
        }
        ListNode temp = loop1.next;//标记入环点
        while (temp != loop1){//循环一周
            if(temp == loop2){//找到另一个入环点，相交
                return true;
            }
            temp = temp.next;
        }
        return false;
    }

    public ListNode getLoop(ListNode head){//获取入环点
        if (head == null){
            return null;
        }
        ListNode cur1 = head;
        ListNode cur2 = head;
        while (cur2.next != null){
            cur1 = cur1.next;
            cur2 = cur2.next.next;
            if (cur1 == cur2){//和赋值顺序不能错
                break;
            }
        }
        cur2 = head;
        while (cur1 != cur2){
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }

    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }
}
